package com.carl.leetcode.listAndDC;

/**
 * Created by carlXie on 2016/3/14.
 */
public class MergeTwoSortedLists {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { this.val = x;}
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head, currentNode = null;

        // 确定要返回的新的链表的头节点
        if(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                currentNode = l1;
                l1 = l1.next;
            } else {
                currentNode = l2;
                l2 = l2.next;
            }
        } else {
            if(l1 != null) return l1;
            else if(l2 != null) return l2;
            else return null;
        }

        head = currentNode;

        // 合并两个链表
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                currentNode.next = l1;
                l1 = l1.next;
            } else {
                currentNode.next = l2;
                l2 = l2.next;
            }

            currentNode = currentNode.next;
        }

        if(l1 != null) {
            currentNode.next = l1;
        } else {
            currentNode.next = l2;
        }
        return head;
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return mergeKLists(lists, 0, lists.length - 1);
    }

    private static ListNode mergeKLists(ListNode[] lists, int leftIndex, int rightIndex) {
        if(leftIndex == rightIndex)
            return lists[leftIndex];
        else if(leftIndex + 1 == rightIndex)
            return mergeTwoLists(lists[leftIndex], lists[rightIndex]);
        else {
            int mid = (leftIndex + rightIndex) / 2;
            return mergeTwoLists(mergeKLists(lists, leftIndex, mid), mergeKLists(lists, mid + 1, rightIndex));
        }
    }


    public static void main(String[] args) {

    }
}
